package leetcode100

// TODO 脑筋急转弯 【-】 下一个排列
// TODO https://leetcode.cn/problems/next-permutation/solution/jie-fa-hen-jian-dan-jie-shi-qi-lai-zen-yao-jiu-na-/

func nextPermutation(nums []int) {
	n := len(nums)
	i := n - 2 // 向左遍历，i从倒数第二开始是为了nums[i+1]要存在

	for i >= 0 && nums[i] >= nums[i+1] { // 寻找第一个小于右邻居的数
		i--
	}
	// 这个数在数组中存在，从它身后挑一个数，和它换
	if i >= 0 {
		j := n - 1                         // 从最后一项，向左遍历
		for j >= 0 && nums[i] >= nums[j] { // 寻找第一个大于 nums[i] 的数
			j--
		}
		nums[i], nums[j] = nums[j], nums[i]
	}

	// 交换之后, 交换为后面肯定是递减排列, 后面的递减排列在翻转一下即可
	// 如果 i = -1，说明是递减排列，如 3 2 1，也可以通过翻转变为：1 2 3
	l, r := i+1, len(nums)-1
	for l < r { // i 右边的数进行翻转，使得变大的幅度小一些
		nums[l], nums[r] = nums[r], nums[l]
		l++
		r--
	}
}
